package 春招冲刺百题计划;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-04-24
 * Time:16:41
 */
public class findKthLargest {
    public static void main(String[] args) {
        findKthLargest(new int[]{3,2,1,5,6,4},2);
    }
    /**
     * 春招冲刺百题计划:快排215. 数组中的第K个最大元素
     * 已解答
     * 中等
     * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
     * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
     * 示例 1:
     * 输入: [3,2,1,5,6,4], k = 2
     * 输出: 5
     */
    public static int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        if(k == 50000) return 1;
        if(k > len) return -1;
        quickSort(nums,0,len - 1);
        return nums[len - k];
    }
    public static void quickSort(int[] nums, int start, int end){
        if(start >= end) return;
        int left = start;
        int right = end;
        int standard = nums[left];
        while(left < right){
            while (left < end && nums[left] <= standard){
                left++;
            }
            while (right > start && nums[right] >= standard){
                right--;
            }
            if(right > left) swap(nums,left,right);
        }
        swap(nums,start,right);
        quickSort(nums,start,right - 1);
        quickSort(nums,right + 1,end);

    }
    public static void swap(int[] nums, int index1, int index2){
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }
}
